{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If All 1's Are at Least Length K Places Away"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kLengthApart"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #是否所有 1 都至少相隔 k 个元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由若干 <code>0</code> 和 <code>1</code> 组成的数组 <code>nums</code> 以及整数 <code>k</code>。如果所有 <code>1</code> 都至少相隔 <code>k</code> 个元素，则返回 <code>True</code> ；否则，返回 <code>False</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/03/sample_1_1791.png\" style=\"width: 214px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,0,0,0,1,0,0,1], k = 2\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>每个 1 都至少相隔 2 个元素。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/05/03/sample_2_1791.png\" style=\"height: 86px; width: 160px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,0,0,1,0,1], k = 2\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>第二个 1 和第三个 1 之间只隔了 1 个元素。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,1,1,1,1], k = 0\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [0,1,0,1], k = 1\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= nums.length</code></li>\n",
    "\t<li><code>nums[i]</code> 的值为 <code>0</code> 或 <code>1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-all-1s-are-at-least-length-k-places-away](https://leetcode.cn/problems/check-if-all-1s-are-at-least-length-k-places-away/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-all-1s-are-at-least-length-k-places-away](https://leetcode.cn/problems/check-if-all-1s-are-at-least-length-k-places-away/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,0,0,1,0,0,1]\\n2', '[1,0,0,1,0,1]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "\n",
    "        if nums[0] == 1:\n",
    "            \n",
    "            sign = 0\n",
    "\n",
    "        else:\n",
    "\n",
    "            sign = -1\n",
    "\n",
    "        for i in range(1,len(nums),1):\n",
    "\n",
    "            if nums[i] == 1:\n",
    "\n",
    "                print(i)\n",
    "\n",
    "                if sign == -1:\n",
    "                    \n",
    "                    sign = i\n",
    "\n",
    "                elif k > i - sign - 1:\n",
    "\n",
    "                        return False\n",
    "                else:\n",
    "\n",
    "                    sign = i\n",
    "\n",
    "        return True\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = k # 处理第一个 1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                if k > cnt: return False\n",
    "                cnt = 0 # 遇到 1 从新记数\n",
    "            else: cnt += 1\n",
    "        return True\n",
    "        \n",
    "        # left = -inf\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] == 1:\n",
    "        #         if i - left - 1 < k: return False\n",
    "        #         left = i\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        p = -1\n",
    "        n = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 0 and p != -1:\n",
    "                n += 1\n",
    "                continue\n",
    "            if nums[i] == 1:\n",
    "                if p != -1 and n < k: return False\n",
    "                p = i \n",
    "                n = 0\n",
    "        return True\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        left = 0\n",
    "        right = 0\n",
    "        n = len(nums)\n",
    "        distance_ok = True\n",
    "\n",
    "        while nums[left] != 1 and left < n - 1:\n",
    "            left += 1\n",
    "        right = left + 1\n",
    "\n",
    "        while right < n and distance_ok:\n",
    "            if nums[right] == 1 and right - left - 1 < k:\n",
    "                distance_ok = False\n",
    "\n",
    "            elif nums[right] == 1 and right - left - 1 >= k:\n",
    "                left = right\n",
    "                right += 1\n",
    "\n",
    "            elif nums[right] != 1:\n",
    "                right += 1\n",
    "\n",
    "        return distance_ok\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cnt = k # 处理第一个 1\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                if k > cnt: return False\n",
    "                cnt = 0 # 遇到 1 从新记数\n",
    "            else: cnt += 1\n",
    "        return True\n",
    "        \n",
    "        # left = -inf\n",
    "        # for i in range(len(nums)):\n",
    "        #     if nums[i] == 1:\n",
    "        #         if i - left - 1 < k: return False\n",
    "        #         left = i\n",
    "        # return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cou = 0\n",
    "        flag=1\n",
    "        for n in nums:\n",
    "            if flag==0:\n",
    "                if n==1:\n",
    "                    if cou<k:return False\n",
    "                    cou=0\n",
    "                    continue\n",
    "                else:\n",
    "                    cou+=1\n",
    "                    continue\n",
    "            if flag==1:\n",
    "                if n==1:flag-=1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cur, cnt = -1, 0\n",
    "\n",
    "        for i, j in enumerate(nums):\n",
    "            if j == 1:\n",
    "                cnt += 1\n",
    "\n",
    "                if cnt > 1:\n",
    "                    if i - cur - 1 < k:\n",
    "                        return False\n",
    "                    cur = i\n",
    "                else:\n",
    "                    cur = i\n",
    "\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cur, cnt = -1, 0\n",
    "\n",
    "        for i, j in enumerate(nums):\n",
    "            if j == 1:\n",
    "                cnt += 1\n",
    "\n",
    "                if cnt > 1:\n",
    "                    if i - cur - 1 < k:\n",
    "                        return False\n",
    "                    cur = i\n",
    "                else:\n",
    "                    cur = i\n",
    "\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cou = 0\n",
    "        flag=1\n",
    "        for n in nums:\n",
    "            if flag==0:\n",
    "                if n==1:\n",
    "                    if cou<k:return False\n",
    "                    cou=0\n",
    "                else:cou+=1\n",
    "            if flag==1:\n",
    "                if n==1:flag-=1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        cou = 0\n",
    "        flag=1\n",
    "        for n in nums:\n",
    "            if flag==0:\n",
    "                if n==1:\n",
    "                    if cou<k:return False\n",
    "                    cou=0\n",
    "                else:\n",
    "                    cou+=1\n",
    "            if flag==1:\n",
    "                if n==1:flag-=1\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        start = 0\n",
    "        min_diff = len(nums)\n",
    "        while start < len(nums):\n",
    "            while start < len(nums) and nums[start] == 0:\n",
    "                start = start + 1\n",
    "            end = start + 1\n",
    "            while end < len(nums) and nums[end] == 0:\n",
    "                end = end + 1\n",
    "            if end < len(nums):\n",
    "                diff = end - start - 1\n",
    "                print(start, end, diff)\n",
    "                if diff < min_diff:\n",
    "                    min_diff = diff\n",
    "            start = end\n",
    "\n",
    "            \n",
    "        print(min_diff)\n",
    "        return min_diff >= k\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        pre = -k - 1\n",
    "        for i, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                print(i, pre)\n",
    "                if i - pre - 1 < k:\n",
    "                    return False\n",
    "                else:\n",
    "                    pre = i\n",
    "        return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        n = len(nums)\n",
    "        s = [0] * n\n",
    "        s[0] = nums[0]\n",
    "        count = 0\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(1, n):\n",
    "            print(count)\n",
    "            s[i] = s[i-1] + nums[i]\n",
    "            if s[i] == s[i-1]:\n",
    "                count += 1\n",
    "            else:\n",
    "                ans = min(ans, count + 1) if s[i-1] == 0 else min(ans, count)\n",
    "                count = 0\n",
    "        \n",
    "        if k <= ans: return True\n",
    "        else: return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        stack=[]\n",
    "        for ind,i in enumerate(nums):\n",
    "            if i==1:\n",
    "                stack.append(ind)\n",
    "        stack=sorted(stack,reverse=True)\n",
    "        for i in range(0,len(stack)-1):\n",
    "            if stack[i]-stack[i+1]<=k:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        temp = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] & 1 == 1:\n",
    "                temp.append(i)\n",
    "        for i in range(len(temp) - 1):\n",
    "            if temp[i] + k >= temp[i + 1]:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        # 一轮扫记录所有1的index\n",
    "        p = 0\n",
    "        index_lst = []\n",
    "        while p < len(nums):\n",
    "            if nums[p] == 1:\n",
    "                index_lst.append(p)\n",
    "            p += 1\n",
    "        # 只要相邻的隔了两个以上元素就行\n",
    "        p = 0\n",
    "        while p < len(index_lst) - 1:\n",
    "            if index_lst[p+1] - index_lst[p] - 1< k :\n",
    "                return False\n",
    "            p += 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        index1=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                if index1 and (i-index1[-1]-1)<k:\n",
    "                    return False\n",
    "\n",
    "                index1.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        queue=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                if queue:\n",
    "                    if i-queue[-1]-1>=k:\n",
    "                        pass\n",
    "                    else:\n",
    "                        return False\n",
    "                queue.append(i)\n",
    "\n",
    "        return True\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        index1=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                if index1 and (i-index1[-1]-1)<k:\n",
    "                    return False\n",
    "\n",
    "                index1.append(i)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        stack=[]\n",
    "        for ind,i in enumerate(nums):\n",
    "            if i==1:\n",
    "                stack.append(ind)\n",
    "        stack=sorted(stack,reverse=True)\n",
    "        for i in range(0,len(stack)-1):\n",
    "            if stack[i]-stack[i+1]<=k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        a = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                if a and i-a[-1]-1<k:\n",
    "                    return False\n",
    "                a.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        count=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                count.append(i)\n",
    "        if count==[] or len(count)==1: \n",
    "            return True\n",
    "        else:\n",
    "            length=count[1]-count[0]-1\n",
    "            for j in range(len(count)-1):\n",
    "                c=count[j+1]-count[j]-1\n",
    "                length=min(length,c)\n",
    "            return length==k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        hsmap = collections.defaultdict(list)\n",
    "        for i in range(len(nums)):\n",
    "            if len(hsmap[1])>0 and nums[i]==1:\n",
    "                if i-hsmap[1][-1]<=k:\n",
    "                    return False\n",
    "            if nums[i]==1:\n",
    "                hsmap[1].append(i)\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        pos = []\n",
    "        for i, v in enumerate(nums):\n",
    "            if v == 1:\n",
    "                pos.append(i)\n",
    "        if len(pos) >= 2:\n",
    "            dis = [pos[i+1]-pos[i]-1 for i in range(len(pos)-1)]\n",
    "            return min(dis) >= k\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        index1=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                if index1 and (i-index1[-1]-1)<k:\n",
    "                    return False\n",
    "\n",
    "                index1.append(i)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        if not nums: return True\n",
    "        pos = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1: pos.append(i)\n",
    "        if not pos: return True\n",
    "        for i in range(len(pos) - 1):\n",
    "            if pos[i] + k >= pos[i + 1]: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        a=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                a.append(i)\n",
    "\n",
    "        for i in range(len(a)-1):\n",
    "            if a[i+1]-a[i]-1<k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        d=[i for i in range(len(nums)) if nums[i]]\n",
    "        for i in range(len(d)-1):\n",
    "            c=d[i+1]-d[i]-1\n",
    "            if c<k:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\r\n",
    "        tmp = [ii for ii, i in enumerate(nums) if i]\r\n",
    "        for i in range(1, len(tmp)):\r\n",
    "            if tmp[i] - tmp[i - 1] <= k:\r\n",
    "                return False\r\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        a = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                a.append(i)\n",
    "        \n",
    "        for i in range(1, len(a)):\n",
    "            if a[i] - a[i-1] < k+1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        res=[]\n",
    "        if 1 not in nums:\n",
    "            return True\n",
    "        if 0 not in nums:\n",
    "            if k==0:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        for p in range(0,len(nums)):\n",
    "            if nums[p]  ==1:\n",
    "                res.append(p+1)\n",
    "        for i in range(len(res)):\n",
    "            for j in range(0,len(res)-(i+1)):\n",
    "                if abs(res[j]-res[j+1])-1<k:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        res = []\n",
    "        for i, n in enumerate(nums):\n",
    "            if n == 1:\n",
    "                res.append(i)\n",
    "        for j in itertools.pairwise(res):\n",
    "            if j[1] - j[0] <= k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        if nums.count(1)<=1:\n",
    "            return True\n",
    "        index=[]\n",
    "        for i in range(0,len(nums)):\n",
    "            if nums[i]==1:\n",
    "                index.append(i)\n",
    "        for i in range(0,len(index)-1):\n",
    "            index[i]=index[i+1]-index[i]-1\n",
    "        if min(index)>=k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        a = []\n",
    "        count = 0\n",
    "\n",
    "        for i in nums:\n",
    "            if i == 1:\n",
    "                a.append(count)\n",
    "            count += 1\n",
    "        \n",
    "        count = 0\n",
    "        while count < len(a) - 1:\n",
    "            if a[count+1] - a[count] - 1 < k:\n",
    "                return False\n",
    "            count += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        dp=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                dp.append(i)\n",
    "\n",
    "        if len(dp)<=1:\n",
    "            return True\n",
    "        print(min([dp[i]-dp[i-1] for i in range(1,len(dp))]))\n",
    "        return min([dp[i]-dp[i-1] for i in range(1,len(dp))])>=k+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                res.append(i)\n",
    "        res.sort()\n",
    "        for i in range(len(res)-1):\n",
    "            derta = res[i+1]-res[i]-1\n",
    "            print(derta)\n",
    "            if derta<k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        idxs = []\n",
    "        res = []\n",
    "        for idx, num in enumerate(nums):\n",
    "            if num == 1:\n",
    "                idxs.append(idx)\n",
    "        if len(idxs) >= 2:\n",
    "            for i in range(len(idxs)-1):\n",
    "                re = idxs[i+1]- idxs[i]\n",
    "                res.append(re)\n",
    "            ree = sorted(res)\n",
    "            if ree[0] >= k+1:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        else:\n",
    "            return True\n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:        \n",
    "        temp=[i for i in range(len(nums)) if nums[i]==1]\n",
    "        if len(temp)<=1:\n",
    "            return True\n",
    "        return all([(x-y)>=k+1 for x,y in zip(temp[1:],temp)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        res = True\n",
    "        vals = nums.copy()\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        for i in range(len(nums)-k):\n",
    "            if nums[i+k]-nums[i] > 1 or nums[i+k]-nums[i] == vals[i+k] == vals[i] == 1:\n",
    "                res = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        l=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                l.append(i)\n",
    "        for i in range(1,len(l)):\n",
    "            if l[i]-l[i-1] <=k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        d = []\n",
    "        for i,num in enumerate(nums):\n",
    "            if num: d.append(i)\n",
    "        return all(f-b>k for b,f in pairwise(d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        idxs = [i for i in range(len(nums)) if nums[i]==1]\n",
    "        dis = [idxs[j+1]-idxs[j]-1 for j in range(len(idxs)-1)]\n",
    "        if all([dis[j]>=k for j in range(len(dis))]):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        list_new = []\n",
    "        count = 0\n",
    "        if 1 not in nums:\n",
    "            return bool(1)\n",
    "        else:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 1:\n",
    "                    list_new.append(i)\n",
    "            for j in range(1,len(list_new)):\n",
    "                if list_new[j]-list_new[j-1]-1 >= k:\n",
    "                    count +=1\n",
    "            if count == len(list_new)-1:\n",
    "                return bool(1)\n",
    "            else:\n",
    "                return bool(0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        A = [i for i,x in enumerate(nums) if x]\n",
    "        return all(b-a>k for a,b in pairwise(A))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "      result = ''\n",
    "      for i in nums:\n",
    "        result += str(i)\n",
    "      m = result.split('1')[1:-1]\n",
    "      return all([len(x) >= k for x in m])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        list_new = []\n",
    "        count = 0\n",
    "        if 1 not in nums:\n",
    "            return bool(1)\n",
    "        else:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] == 1:\n",
    "                    list_new.append(i)\n",
    "            for j in range(1,len(list_new)):\n",
    "                if list_new[j]-list_new[j-1]-1 >= k:\n",
    "                    count +=1\n",
    "            if count == len(list_new)-1:\n",
    "                return bool(1)\n",
    "            else:\n",
    "                return bool(0)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        try:\n",
    "            i = nums.index(1)\n",
    "            res = [i]\n",
    "            for j in range(i+1,len(nums)):\n",
    "                if nums[j] == 1:\n",
    "                    if j-res[-1] < k+1:\n",
    "                        return False\n",
    "                    res.append(j)\n",
    "            return True\n",
    "        except:\n",
    "            return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums, k: int) -> bool:\n",
    "        S=''.join(map(str,nums))\n",
    "        i=S.find('1')\n",
    "        while i!=-1:\n",
    "            a=S.find('1',i+1)\n",
    "            if a==-1:break\n",
    "            if abs(a-i)<=k:return False\n",
    "            i=a\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        strnum = ''.join(map(str, nums))\n",
    "        strnum.strip('0')\n",
    "        number = int(strnum, base=2)\n",
    "        number>>=1\n",
    "        count = 0\n",
    "        ans = float('inf')\n",
    "        while number:\n",
    "            if number & 1:\n",
    "                ans = min(ans, count)\n",
    "                count = 0\n",
    "            count += 1\n",
    "            number >>= 1\n",
    "        return ans >= k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = str(nums[i])\n",
    "        s= ''.join(nums)\n",
    "        s = s.split('1')[1:-1]\n",
    "        for zeros in s:\n",
    "            if len(zeros) < k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        ones = [i for i in range(len(nums)) if nums[i]==1]\n",
    "        diff = [x-y-1 for x,y in zip(ones[1:],ones[:-1])]\n",
    "        return all([True if x>=k else False for x in diff])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = str(nums[i])\n",
    "        s= ''.join(nums)\n",
    "        s = s.split('1')[1:-1]\n",
    "        for zeros in s:\n",
    "            if len(zeros) < k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        lis=[]\n",
    "        for index,integer in enumerate(nums):\n",
    "            if integer==1:\n",
    "                lis.append(index)\n",
    "        if len(lis)<=1:\n",
    "            return True\n",
    "        ans=[]\n",
    "        for i in range(1,len(lis)):\n",
    "            ans.append(lis[i]-lis[i-1])\n",
    "        \n",
    "\n",
    "        return min(ans)>k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        while nums and nums[0] == 0:\n",
    "            nums.pop(0)\n",
    "        \n",
    "        while nums and nums[-1] == 0:\n",
    "            nums.pop()\n",
    "        s = ''.join([str(x) for x in nums])\n",
    "        # print(s)\n",
    "        ss = s.split('1')\n",
    "        # print(ss)\n",
    "        if ss and not ss[0]:\n",
    "            ss.pop(0)\n",
    "        if ss and not ss[-1]:\n",
    "            ss.pop()\n",
    "        # print(ss)\n",
    "        if not ss: return True\n",
    "        ans = min([len(c) for c in ss])\n",
    "        if ans >= k:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        list1 = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                list1.append(i)\n",
    "        for i in range(1, len(list1)):\n",
    "            if list1[i] - list1[i-1] <= k:\n",
    "                return False\n",
    "        return True\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        lst = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                lst.append(i)\n",
    "        for j in range(len(lst) - 1):\n",
    "            if lst[j + 1] - lst[j] - 1 < k:\n",
    "                return False\n",
    "        return True\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        \n",
    "        l = []\n",
    "        for i,ele in enumerate(nums):\n",
    "            if (ele == 1):\n",
    "                l.append(i)\n",
    "\n",
    "\n",
    "        for i,ele in enumerate(l):\n",
    "            if (ele==l[-1]):\n",
    "                return True\n",
    "            if (l[i+1]-ele-1>=k):\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        lst = []\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == 1:\n",
    "                lst.append(i)\n",
    "        for j in range(len(lst) - 1):\n",
    "            if lst[j + 1] - lst[j] - 1 < k:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        res=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]==1:\n",
    "                res.append(i)\n",
    "        for i in range(1,len(res)):\n",
    "            if res[i]-res[i-1]<k+1:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        index_list = [i for i, j in enumerate(nums) if j == 1]\n",
    "        return all(b - a - 1>= k for a,b in pairwise(index_list))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        return all(b - a - 1>= k for a,b in pairwise([i for i, j in enumerate(nums) if j == 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        return all(b - a - 1>= k for a,b in pairwise([i for i, j in enumerate(nums) if j == 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kLengthApart(self, nums: List[int], k: int) -> bool:\n",
    "        return all(b - a - 1>= k for a,b in pairwise([i for i, j in enumerate(nums) if j == 1]))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
